package algorithm.leetcode.medium;

/*
    在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
    你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。
    你从其中的一个加油站出发，开始时油箱为空。
    如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/12/1
 */
public class Question134 {

    public static void main(String[] args) {

    }


    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;

        while (i < n) {
            // 加的油之和
            int sumOfGas = 0;
            // 消费的油之和
            int sumOfCost = 0;
            // 记录走过的站
            int count = 0;

            while (count < n) {
                // 环形
                int j = (i + count) % n;
                // 加油
                sumOfGas += gas[j];
                // 消耗
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {
                    break;
                }
                // 继续走
                count++;
            }
            // 发现走了一圈
            if (count == n) {
                return i;
            }else {
                // 不行的话 从下一个站点开始 检查
                i = i + count + 1;
            }
        }
        // 都不满足
        return -1;
    }
}
